class Solution {
public:
    int waysToStep(int n) {
        //状态表示 dp[i] 到达第i阶的方法数
        //状态转移方程 dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
        //初始化   "dp[0]=1",dp[1]=1,dp[2]=2
        //返回值 dp[n]
        //空间优化 n0 n1 n2
        if(n<3)
            return n?n:1;
        long long n0=1,n1=1,n2=2;
        for(int i=3;i<=n;i++){
            int ni=(n0+n1+n2)%1000000007;
            n0=n1;n1=n2;n2=ni;
        }
        return n2;
    }
};